package Example_practice02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Activity{
    public int start;
    public int endTime;
    public Activity(int start,int endTime){
        this.start=start;
        this.endTime=endTime;
    }
}
public class SelectActivity {
    //贪心算法实现活动安排问题
    public static List<Activity> selectArrangement(Activity[] activities){
        //定义活动收容集合
        List<Activity> activityList=new ArrayList<>();
        //排序,按照结束时间从小到大排
        Arrays.sort(activities,(a1,a2)->
                Integer.compare(a1.endTime, a2.endTime));

        //第一个活动加入收容集合
        activityList.add(activities[0]);
        //第一个参考的结束时间
        int preEndTime=activities[0].endTime;

        //贪心算法选择
        for (int i=1;i<activities.length;i++){
            //如果当前活动的开始时间大于于前一个活动的结束时间，加入集合
            if (activities[i].start>=preEndTime){
                activityList.add(activities[i]);
                preEndTime=activities[i].endTime;//更新结束时间
            }
            //如果当前活动开始时间小于前一个活动的结束时间，但是当前活动的结束时间也小于前一个活动的结束时间，替换
            else if (activities[i].endTime<preEndTime){
                activityList.remove(i-1);
                activityList.add(activities[i-1]);
                preEndTime=activities[i].endTime;
            }
        }
        return activityList;
    }
    public static void main(String[] args){
        Activity[] activities={new Activity(0,4),
                new Activity(0,2),
                new Activity(2,3),
                new Activity(3,4),
                new Activity(5,6),
                new Activity(5,7)
        };
        List<Activity> SelectArrangement=selectArrangement(activities);
        System.out.println("最大的活动收集集合为：");
        for (Activity activity:SelectArrangement){
            System.out.println(activity.start+","+activity.endTime);
        }
    }
}
